//
//  Problem14.swift
//  LeetCode - 14 最长公共前缀
//
//  Created by 毕武侠 on 2020/7/4.
//  Copyright © 2020 毕武侠. All rights reserved.
//

import UIKit
/*
 最长公共前缀
 编写一个函数来查找字符串数组中的最长公共前缀。
 如果不存在公共前缀，返回空字符串 ""。

 示例 1:      输入: ["flower","flow","flight"]      输出: "fl"
 示例 2:      输入: ["dog","racecar","car"]         输出: ""
 解释: 输入不存在公共前缀。
 
 说明:所有输入只包含小写字母 a-z 。
 */

class Problem14: NSObject {
    
    func test() {
        let strLists = ["aa", "a", "c"]
        print(strLists, " = ", longestCommonPrefix(strLists))
        
        let strLists1 = ["c","c"]
        print(strLists1, " = ", longestCommonPrefix(strLists1))
        
        
        let strLists2 = ["",""]
        print(strLists2, " = ", longestCommonPrefix(strLists2))
        
        let strLists3:[String] = []
        print(strLists3, " = ", longestCommonPrefix(strLists3))
        
        
        let strLists4:[String] = ["flower","flow","flight"]
        print(strLists4, " = ", longestCommonPrefix(strLists4))
        
        let strLists5:[String] = ["dog","racecar","car"]
        print(strLists5, " = ", longestCommonPrefix(strLists5))
    }
    
    func longestCommonPrefix(_ strs: [String]) -> String {
        if strs.count == 0 {
            return ""
        } else if strs.count == 1 {
            return strs[0]
        }
        
        let strFirst = strs[0]
        var i: Int = 0
        while i < strFirst.count {
            var tempSub:Substring = ""
            for (j, str) in strs.enumerated() {
                if str == "" {
                    return ""
                }
                if i >= str.count {
                    return str
                }
                
                let index = str.index(str.startIndex, offsetBy: i)
                let nindex = str.index(str.startIndex, offsetBy: i+1)
                let substr = str[index..<nindex]
                
//                print("substr = ", substr)
                if j == 0 {
                    tempSub = substr
                } else {
                    if tempSub != substr {
                        return String(str[..<index])
                    }
                }
            }
            i += 1
        }
        
        let index = strs[0].index(strs[0].startIndex, offsetBy: i)
        return String(strs[0][..<index])
    }
}
